/*
插入排序是一种简单的排序算法，
    其基本思想是将数据分为已排序和未排序的部分，
    然后逐一将未排序的元素插入到已排序部分的正确位置。尽管插入排序在大多数情况下性能不如高级排序算法，但在数据集较小或接近排序状态的情况下表现良好。

*/

#include <stdio.h>

// 插入排序函数
void insertion_sort(int arr[], int size) {
    // 遍历数组中的每个元素，从第二个开始
    for (int i = 1; i < size; i++) {
        int key = arr[i];  // 当前要插入的元素
        int j = i - 1;

        // 向左移动大于 key 的元素
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 向右移动
            j--;
        }

        // 将 key 插入到正确位置
        arr[j + 1] = key;
    }
}

int main() {
    // 示例数组
    int arr[] = {5, 2, 9, 1, 5, 6};
    int size = sizeof(arr) / sizeof(arr[0]);

    // 执行插入排序
    insertion_sort(arr, size);

    // 输出排序结果
    printf("排序后的数组: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}
